#include <bits/stdc++.h>
using namespace std;

/*
594. 最长和谐子序列
已解答
简单
相关标签
premium lock icon
相关企业
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

 

示例 1：

输入：nums = [1,3,2,2,5,2,3,7]

输出：5

解释：

最长和谐子序列是 [3,2,2,2,3]。

示例 2：

输入：nums = [1,2,3,4]

输出：2

解释：

最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。

示例 3：

输入：nums = [1,1,1,1]

输出：0

解释：

不存在和谐子序列。

 

提示：

1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109
*/

// 法一
class Solution {
public:
    int findLHS(vector<int>& nums) {
        // 排序后双指针 滑动窗口
        sort(nums.begin(), nums.end());
        int max_len = 0;        // 当前找到的最长和谐子序列长度
        int left = 0;
        for (int right = 0; right < nums.size(); right++) {
            // 当窗口内最大值与最小值差超过1时，收缩左边界
            while (nums[right] - nums[left] > 1)    left++;
            // 若当前窗口满足和谐子序列条件，更新最大长度
            if (nums[right] - nums[left] == 1)  max_len = max(max_len, right + 1 - left);
        }
        return max_len;
    }
};

// 法二
class Solution {
public:
    int findLHS(vector<int>& nums) {
        // 哈希
        // 对于哈希表中的每个数字，检查是否存在比它大1的数字。如果存在，计算这两个数字的出现次数之和，并更新最大长度。
        // 遍历返回结果
        unordered_map<int, int> freq;
        // 先进哈希表
        for (int num : nums)    freq[num]++;

        // 最大和谐子序列
        int max_len = 0;
        for (auto& [num, count] : freq) {
            // 满足条件 就更新最大值
            if (freq.count(num + 1))    max_len = max(max_len, count + freq[num + 1]);
        }
        return max_len;
    }
};